The present invention relates to computer graphics systems, and more particularly, to compressing and decompressing three-dimensional graphics data.
In recent years, demand for high performance graphics systems that can render complex three-dimensional (3D) objects and scenes has increased substantially. This increase is at least in part due to new applications such as computer-generated animation for motion pictures, virtual reality simulators/trainers, and interactive computer games. These new applications place tremendous demands upon graphics systems. One area in which particularly high demands are placed on graphics systems is bandwidth. This is because 3D graphics data may be several orders of magnitude larger than comparable 2D graphics data. For example, simple 2D graphics data may simply include color information for each pixel displayed. In contrast, 3D graphics data may include xyz position information, normal information, color information, transparency information, texture map information, reflectivity information, and additional information. This information is collectively referred to herein as xe2x80x9cvertex component informationxe2x80x9d.
A number of different techniques have been proposed to reduce the bandwidth requirements of 3D graphics data. One such technique is known as geometry compression. One type of geometry compression is described in detail in U.S. Pat. No. 5,793,371, issued on Aug. 11, 1998, entitled xe2x80x9cMethod and Apparatus for Geometric Compression of Three-Dimensional Graphics Dataxe2x80x9d by Michael F. Deering, which is incorporated herein by reference in its entirety. Generally speaking, geometry compression relies upon reusing vertices (among other techniques) to reduce the size of the 3D graphics data. To describe a 3D object, a number of points typically on the surface of the object are specified. The points are referred to as vertices. Each vertex may have a number of attributes associated with it. For example, each vertex may have color and xyz position information associated with it. Other attribute that may be associated with vertices are texture map coordinates, index of refraction information, polarization information, displacement information, normals, color, and transparency information. For example, if a texture of marble is texture-mapped onto a sphere, each vertex on the sphere may have a texture map coordinate specifying how the texture should be applied (i.e., which part of the sample texture should be mapped to that particular vertex). A normal is a vector from the vertex that is perpendicular to the surface of the object at the vertex. This is illustrated in the 3D object of FIG. 1. The 3D object may be represented by a number of vertices (represented as dots in the figure). Normals for the object are represented by arrows that extend perpendicularly from the object""s surface at each vertex point.
Normals are vectors or directions in three-dimensional space. In the context of 3D graphics, normals (also called surface normals) may each indicate the local orientation of the surface of a 3D graphics object. Since the starting point of the vector is known from the xyz coordinates of the vertex, the normal may be specified with an x-component, a y-component, and a z-component (referred to as Nx, Ny, and Nz, respectively). In some embodiments, these components may be specified relative to the vertex. This embodiment is illustrated in FIG. 2. However, other forms for specifying normals are also possible. Furthermore, in some implementations the normal components are themselves normalized. A normalized normal is one in which the sum of the squares of Nx, Ny, and Nz equals a constant one.
In 3D graphics, vertices are typically grouped together to form polygons such as triangles, as shown in FIG. 3. By definition, a triangle has three vertices. However, many times triangles share vertices. In FIG. 3, vertices 1-2-3 form a first triangle and vertices 2-3-4 form a second triangle. Thus, vertices 2 and 3 are shared between the two triangles. 3D objects may be represented by specifying a number of triangles. This is shown in FIG. 4.
However, specifying all of the information associated with each vertex (e.g., xyz location, color, normal, etc.) every time a vertex is referenced as part of a triangle is inefficient. Instead, the information about a vertex can be stored (e.g., when it is first transmitted) for later use. Then, when the vertex is needed again for another triangle, the vertex may be read from storage instead of having to be re-transmitted. The vertex information may be stored in a xe2x80x9cmesh bufferxe2x80x9d and then reused. This may advantageously reduce the amount of information that must be transmitted and may thus save bandwidth. This is illustrated in FIG. 5.
To efficiently reuse vertices, the triangles may be organized into a mesh (e.g., a predetermined number of neighboring vertices. The mesh may then be encoded as one or more xe2x80x9ctriangle-stripsxe2x80x9d. For example, in FIG. 6 of the application, the triangle strip may start with the following triangles: 6,1,7; 1,7,2; 7,2,3; 7,3,4; 7,4,8; 4,8,5; et seq.
As this pattern shows, once the triangle strip is started many subsequent triangles may be specified using only a single new vertex. For example, after triangle 6,1,7 has been constructed, triangle 1,7,2 may be constructed using only one new vertex (i.e., vertex 2). Thus, each vertex in the triangle strip may describe from ⅓ to one triangle. For example, in the list above, vertex 6 describes ⅓ of triangle 6,1,7. Vertex 2 describes one triangle 1,7,2. In some cases, a vertex may even describe two or even more triangles.
While a number of different formats are possible, one type of generalized triangle strip may be defined as follows (encoding the 3D object from FIG. 6):
R6, O1, O7, O2, O3, M4, M8, O5, O9, O10, M11
M17, M16, M9, O15, O8, O7, M14, O13, M6,
O12, M18, M19, M20, M14, O21, O15, O22, O16,
O23, O17, O24, M30, M29, M28, M22, 021, M20,
M27, O26, M19, O25, O18
In the notation above, R is a restart tag (indicating that a new mesh is beginning), O denotes replace oldest, and M denotes replace middle. The operation of this type of generalized triangle strip is illustrated in FIGS. 7A-7H.
In some embodiments, the terms xe2x80x9coldestxe2x80x9d and xe2x80x9cmiddlexe2x80x9d may be visualized as representing three registers that are used in forming triangles from the triangle strip representation. The sample encoding above is merely one nomenclature that may be used to represent how the vertices of the mesh are being encoded. Different implementations may use other nomenclatures. The example nomenclature uses letters (O and M) to indicate which vertex should be discarded from the three registers when forming a new triangle. O indicates the oldest vertex should be discarded. M indicates the middle vertex should be discarded. R indicates that a section of mesh is being started. This is used to clear the oldest, middle, and newest registers and the mesh buffer, if desired.
While this method reuses vertices, when vertex 8 is referenced a second time (i.e., by the command O8), the vertex is transmitted again. This retransmission of vertices may be reduced or avoided altogether by using a mesh buffer.
Using a similar nomenclature as in the previous example, a generalized triangle mesh utilizing a mesh buffer may be defined as follows (once again encoding the 3D object of FIG. 6):
R6p, O1, O7p, O2, O3, M4, M8p, O5, O9p, O10, M11, O17p, 
M16p, Mxe2x88x923, O15p, Oxe2x88x925, O6, M14p, O13p, M9, O12, M18p, 
M19p, M20p, Mxe2x88x925, 021p, Oxe2x88x927, O22p, Oxe2x88x929, O23, Oxe2x88x9210, Oxe2x88x927,
M30, M29, M28, Mxe2x88x921, Oxe2x88x922, Mxe2x88x923, M27, 026, Mxe2x88x924, O25, Oxe2x88x925
In this implementation, a trailing letter xe2x80x9cpxe2x80x9d denotes xe2x80x9cpush into mesh bufferxe2x80x9d. The number following a capital letter is a vertex number, and a negative number is the mesh buffer reference, in which xe2x80x9cxe2x88x921xe2x80x9d denotes the most recent pushed vertex.
Thus, geometry compression may explicitly push old vertices (e.g., vertices with a trailing letter xe2x80x9cpxe2x80x9d above) into a mesh buffer. These old vertices may be explicitly referenced when the old vertex is again needed. This approach provides a fine control that supports irregular meshes of nearly any shape. As used herein, the term xe2x80x9cmesh bufferxe2x80x9d shall refer to this queue, and the expression xe2x80x9cgeneralized triangle meshxe2x80x9d will refer to a combination of generalized triangle strips and mesh buffer references.
FIGS. 8A-8N illustrate one embodiment of this method graphically. The mesh buffer may be used to store designated vertices (i.e., those followed by a xe2x80x9cpxe2x80x9d). These vertices may later be read out of the mesh buffer (e.g., by a reference with a minus sign such as xe2x80x9cMxe2x88x923xe2x80x9d). This allows vertices to be reused from the mesh buffer instead of having to be retransmitted.
As previously noted, by reducing the size of the 3D graphic data bandwidth may be saved. For example, when programmers are creating a 3D virtual object to be used in a simulation, they may execute a compression program to determine how best to compress the 3D object. The compression program may tessellate or divide the surface of the object into a plurality of vertices, e.g., a NURBs (Non-Uniform Rational B-spline) object. The compression program may then divide the vertices into groups of generalized triangle meshes as described above. These meshes may then be compressed and encoded using a similar process to that described above. The compressed data may then be stored (e.g., on a CD-ROM or DVD-ROM) and/or transmitted (e.g., on the Internet). The bandwidth savings may also apply to buses used for transmission of the 3D geometry data within the graphics system itself.
FIG. 9 illustrates one embodiment of a graphics system 20 configured to utilize compressed 3D geometry data in generalized triangle mesh form. In this embodiment, transmission bandwidth across transmission medium 10 is saved by transmitting 3D graphics data in compressed form using geometry compression in generalized triangle mesh format.
Generally, compressed 3D geometry data is conveyed to graphics system 20 on input bus 10. Geometry decompressor 12 receives the compressed data and decompresses it. A mesh buffer 14 may be used to store vertices that will be reused. As previously described, mesh buffer references may be encoded within the compressed data to indicate which vertices will be reused and thus should be stored in the mesh buffer.
Once a geometric primitive such as a triangle is decompressed, it is conveyed to one of a plurality of transform and lighting processors 18A-N. The transform and lighting processors work independently and in parallel to perform the following functions: (a) transform the vertices forming primitive from their original coordinate reference frame (e.g., object space) into a common reference frame (e.g., world space or screen space); and (b) xe2x80x9clightxe2x80x9d each vertex by determining which light sources affect each vertex and how much they are affected.
Next, the transformed and lit triangles are conveyed to draw processor 22, which is configured to render the transformed and lit primitives and perform other effects such as texture mapping (i.e., applying textures from texture map memory 24). In some embodiments, draw processor 22 may be configured to execute a programmable shader. Shading is the process of calculating the color of each surface as seen in the output image, as well as its shape and position. A programmable shader is a process or procedure that may be executed to compute a value or set of values needed during the drawing or rendering process. Parts of the shading process may include determining the intensity and color of light from various light sources, determining which light sources contribute, determining reflects and transmission of light, and atmospheric effects. Details of programmable shading are described in the book entitled xe2x80x9cThe Renderman Companion: A Programmer""s Guide to Realistic Computer Graphicsxe2x80x9d by Steve Upstill, (Addison-Wesley Publishing. Co., July 1989, ISBN: 0201508680).
Generally, draw processor 22 is configured to rasterize the shaded primitive into frame buffer 28. In most embodiments, frame buffer 28 is double buffered, with one buffer being draw into by draw processor 22 while the second buffer is being read by DACs 30. DACs 30 may read frame buffer 28 asynchronously with respect to draw processor 22. DACs 30 form an output video signal that is typically used to drive a display device such as a CRT monitor or LCD panel display.
For the reasons set forth above, the use of geometry compression is particularly advantageous in high performance graphics systems. However, further increases in the flexibility of geometry compression is desirable. One area in need of more flexibility is the encoding of multiple instances of similar objects. For example, when encoding an automobile, it would be useful to allow the automobile""s wheels to be encoded once and then be reused to generate a total of four wheels. Similarly, when encoding books on the shelves of a library, it may be desirable to encode only a small number of books, and then reuse the books, each time with a different color. Thus, an instruction set for geometry compression that provides the flexibility to reduce the need for re-encoding multiple instances of similar objects is particularly desirable.
The problems outlined above may, in part, be solved by an instruction set and method for geometry compression that includes the ability to specify whether an attribute is global or is associated only with a particular vertex.
In some embodiments the instruction and method may also include support for gosub-type instructions and goto-type instructions. Advantageously, an instruction set that supports one or more of these instructions may provide the additional functionality and flexibility necessary to reduce the need for encoding multiple instances of a particular object.
In some embodiments, gosub-type instructions may be detected during the decompression process. Once detected, the corresponding data is read to determine either the absolute address or the offset of the next instruction to execute (e.g., by following an accompanying pointer). Instructions at the designated address or offset are executed in a sequential fashion until an end-of-subroutine or end of stream instruction (collectively referred to herein as an xe2x80x9ceos-typexe2x80x9d instruction) is detected. Advantageously, if a certain set of instructions are to be applied to a subset of the vertices within a particular mesh, the set of instructions may be specified once for the entire mesh (instead of once for each vertex) and each set of vertices to which the set of instructions will apply is encoded with a gosub-type instruction. In this case, storage space/bandwidth may be saved at the potential expense of increasing the complexity of the decompression processing time. This tradeoff may be particularly desirable when storage space is at a premium and the set of instructions being repeated is substantially longer than the gosub instruction.
In some embodiments, the format of the gosub instruction may be fixed length, (i.e., having a fixed maximum length offset or absolute address to identify the location of the subroutine), or variable length (i.e., having no predetermined length). In addition, the graphics system executing the gosub-type instruction may be configured with a return address stack within which to store the return addresses of each outstanding gosub instruction. This stack may thus allow the execution of nested gosub-type instructions. In some embodiments, the number of nested gosub-type instructions may be limited to a predetermined maximum to prevent stack overflow (e.g., zero, one or two nested gosub-type instructions). However, other configurations are also possible and contemplated.
In some embodiments, the gosub-type instructions may be used in combination with xe2x80x9cset attributexe2x80x9d instructions to rapidly assemble a xe2x80x9cscaffoldxe2x80x9d for rendering three-dimensional objects. Set attribute instructions are instructions that load state information into the graphics system. This state information may be transformation information (e.g., x offset, y offset, and z offset), rotation information, scale information, mirroring information, lighting information and other information. When used in combination, the gosub-type instructions and set attribute instructions may provide greater flexibility when compressing, decompressing, shading, and/or rendering a three-dimensional object that includes multiple instances of similar objects. For example, if an automobile is to be rendered, the decompression unit may be configured to generate the scaffold or control flow for the car. The control flow may progress in the following manner: (a) render body of car; (b) set attributes for the first wheel of the car such as a transformation matrix and light settings; (c) gosub to render the first wheel; (d) eos-type instruction passes control back to attribute-setting routine; (e) set attributes for second wheel of car; (f) gosub to render second wheel; (g) eos-type instruction passes control back to attribute-setting routine; and so on.
In some embodiments, the attribute settings for each wheel may be encoded as immediate data (i.e., stored as part of the set attribute instruction). In other embodiments, the attribute settings for each wheel may be stored separately from the set attribute instruction (e.g., in a table in memory). Having both direct and indirect attribute setting commands may allow greater flexibility in the architecture of the graphics systems configured to execute the instructions.
Depending upon the exact implementation, support for goto-type instructions may also be provided in manner similar to that described above in connection with the gosub-type instruction (albeit without any provisions for storing a return address). As with gosub-type instructions, the goto-type instructions may be either fixed or variable length. Advantageously, goto-type instructions may be utilized in combination with set attribute instructions to provide improved flexibility when compressing or rendering scenes or objects that include multiple instances of three-dimensional objects that vary primarily according to attribute settings (e.g., position and lighting).
As previously noted, in some embodiments the instruction set may include both direct and indirect set attribute commands. Examples of set attribute commands include direct and indirect push and pop commands that push or pop attribute information into and out of a transformation matrix. A transformation matrix is a matrix that is used by the graphics system to rotate, translate, and scale a particular three-dimensional graphics object. In the example above, a transformation matrix would have been used to position each of the four instances of the automobile""s wheels.
In some embodiments the method and instruction set for compression and decompression may also include support for xe2x80x9cswitch to uncompressedxe2x80x9d instructions (referred to herein as xe2x80x9cstopc-typexe2x80x9d instructions). This instruction indicates the termination of processing instructions in compression mode. In some embodiments, a fixed-length null header may be included as part of the stopc-type instruction. Stopc-type instructions may be advantageously used to indicate the beginning or the end of a particular object/scene.
As previously noted, as used herein the terms geometric primitive and graphics primitive are not meant to be limited to traditional triangles, but may include other types of primitives (e.g., dots, lines, polygons, subdivision surfaces, Bezier or NURB surfaces or curves, volume elements, and control surfaces). Similarly, the term xe2x80x9cverticesxe2x80x9d need not be limited to include solely traditional polygon vertices. For example, the vertices referred to herein may also include control vertices for Bezier or NURB surfaces or curves.